package primaryAlgorithm;

public class Code02 {
    public int maxProfit(int[] prices){ // 动态规划解决问题 最大利润问题
        //例子 [7,1,5,3,6,4]
        if (prices.length == 1)
            return 0;
        if (prices.length == 2)
            return Math.max(prices[prices.length-1] - prices[prices.length-2],0);
        int[] answers = new int[prices.length];
        answers[answers.length-1] = 0;
        answers[answers.length-2] = Math.max(prices[prices.length-1] - prices[prices.length-2],0);

        for (int r = answers.length - 3; r >= 0; r--) {
            int up = fun2(r,prices); // up是数组中数值下降前的最高点 也就是最高点卖出的价格
            answers[r] = prices[up] - prices[r] + (up+1<=answers.length-1 ? answers[up+1] : 0);;
        }

        return answers[0];
    }

    private int fun2(int r,int[] prices) {
        while (r<prices.length-1 && prices[r] < prices[r+1])
            r++;
        return r;
    }

    public static void main(String[] args) {
        Code02 code02 = new Code02();
        System.out.println("code02.maxProfit(new int[]{7,1,5,3,6,4}) = " + code02.maxProfit(new int[]{7, 1, 5, 3, 6, 4}));
        System.out.println("code02.maxProfit(new int[]{1,2,3,4,5}) = " + code02.maxProfit(new int[]{1, 2, 3, 4, 5}));
        System.out.println("code02.maxProfit(new int[]{7,6,4,3,1}) = " + code02.maxProfit(new int[]{7, 6, 4, 3, 1}));
    }
}
